package 数据结构.链表;

import java.util.HashSet;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-19
 */
public class JZ23链表中环的入口结点 {

    //双指针 快慢指针
    //1.判断链表是否有环。
    //2.在有环的链表中找到环的入口
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle(pHead);
        if (slow == null)
            return null;

        ListNode fast = pHead;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public ListNode hasCycle(ListNode pHead){
        if(pHead == null || pHead.next == null)
            return null;

        ListNode quick = pHead;
        ListNode slow = pHead;
        while(quick!=null && quick.next !=null ){
            quick = quick.next.next;
            slow = slow.next;
            if (quick == slow)
                return quick;
        }
        return null;
    }


    /*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/

        public ListNode EntryNodeOfLoop33(ListNode pHead) {
            ListNode fast = pHead;
            ListNode slow = pHead;
            if(pHead==null || pHead.next==null)
                return null;
            while(fast!=null && fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
                    break;
                }
            }

            if(fast==null || fast.next==null)
                return null;

            fast = pHead;
            while(fast!=slow){
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }


    //HashSet 的方法
    public ListNode EntryNodeOfLoop2(ListNode pHead){
        HashSet<ListNode> set = new HashSet<>();
        while (pHead!=null){
            if(set.contains(pHead))
                return pHead;

            set.add(pHead);
            pHead = pHead.next;
        }
        return null;
    }


    public static void main(String[] args) {

    }
}
